1. Field of the Invention
The present invention generally relates to the processing of digital signals and more specifically to saturating operators.
2. Description of the Related Art
Such operators have an important technical effect. They are used in many signal processing circuits, for example, in mobile phone voice encoding or decoding circuits, where the coding and decoding algorithms use fractional signed numbers.
Fractional signed numbers are numbers ranging between −1 and +1, generally coded over n bits. These numbers are signed, the bit of rank n (most significant bit) being equal to 1 for negative numbers and to 0 for positive numbers. Precisely, the value assigned to a fractional number of n bits is the value of the corresponding integer in two's complement, divided by 2n−1.
The fractional representation is a means enabling use of calculation units which operate on integers. This results in circuits easier to form at the hardware level than circuits using floating point arithmetics. These circuits also use less memory and consume less power.
A so-called “saturating” operator is an operator performing saturating operations, for example, saturating additions and multiplications.
A saturating operation, which will be designated hereafter with symbol
      +    •    ,is an addition of two fractional signed numbers, the result of which is a fractional signed number. This means that if one of the limiting values of the fractional representation is exceeded in the addition, the result is brought to the exceeded limiting value. Thus, if the saturating addition of two signed fractional numbers coded over n bits provides a result greater than 1, said result is brought down to the maximum value that can be taken by a signed fractional number coded over n bits, that is, 1–2−n+1. Similarly, if the result of a saturating addition is smaller than −1, the result of the addition is brought up to the minimum number that can be represented by means of n bits in a fractional representation of signed numbers, that is, −1.
Similarly, a saturating multiplication, here designated with symbol
      ×    ◯    ,is a multiplication the result of which belongs to the field of fractional signed numbers to which the operands belong. If the result of the multiplication exceeds one of the two limiting values of this representation, it is brought to the exceeded limiting value.
The saturating addition and multiplication are both commutative, but not associative.
A device such as a mobile phone is comprised of a microcontroller, of digital signal processors DSP, and of dedicated hardware blocks DHB. The digital signal processors and the dedicated hardware blocks are used to form a great number of various functions, for example, encryption, Fourier transform calculations, MPEG coding, etc. Many digital processings must further be accurate to within one bit. This means that the processing of a sequence of reference digital samples in a device must provide the same digital sequence as a reference algorithm for the device to be certified, standards bodies, such as the ITU (International Telecommunication Union) or the ETSI (European Telecommunications Standard Institute) being in charge of providing the reference samples/algorithms and of certifying the devices.
To provide an exact result to within one bit, a digital signal processor or a dedicated hardware block generally is comprised of many circuits of MAC (Multiply Accumulate Operator) type.
FIG. 1A shows a sequence of three operators of MAC type in series, MAC1, MAC2, and MAC3. Operator MAC1 receives on three input terminals three operands x1, y1, and s1. In a known manner, operator MAC1 provides a result:
      s    2    =            (                        x                      1            ⁢                                                                ⁢                  x          •                ⁢                                  ⁢                  y          1                    )        ⁢          +      •        ⁢                  s        1            .      
The second operator, MAC2, receives two operands x2, y2, as well as result s2 of operator MAC1. It provides a result equal to:
      s    3    =            (                        x                      2            ⁢                                                                ⁢                  x          •                ⁢                                  ⁢                  y          2                    )        ⁢          +      •        ⁢                  s        2            .      
The third operator, MAC3, receives two operands x3 and y3, as well as the result s3 of operator MAC2. Operator MAC3 provides a result s4 equal to:
      s    4    =            (                        x                      3            ⁢                                                                ⁢                  x                      •            ⁢                                                                ⁢                                  ⁢                  y          3                    )        ⁢          +      •        ⁢                  s        3            .      
The expressions of results s2, s3, and s4 are shown in FIG. 1B.
The number of calculations requiring operators of MAC type is generally very high. To gain space and processing time, it is known to gather the operators by two as illustrated in relation with FIGS. 2A to 2C.
FIG. 2A shows two operators of MAC type, MACk and MACk+1, connected one after the other. Operator MACk receives operands xk and yk and an operand sk coming from the preceding operator. Operator MACk provides a result sk+1 equal to:
      s          k      +      1        =            (                        x                      k            ⁢                                                                ⁢                  x          •                ⁢                                  ⁢                  y          k                    )        ⁢          +      •        ⁢                  s        k            .      
Operator MACk+1 receives operands xk+1, yk+1 and sk+1. It provides a result sk+2 equal to:
      s          k      +      2        =            (                        x                      k            +            1                          ⁢                                  ⁢                  x          •                ⁢                                  ⁢                  y                      k            +            1                              )        ⁢          +      •        ⁢                  s                  k          +          1                    .      
As can be seen in FIG. 2B, which shows the expressions of sk+1 and sk+2, sk+2 is equal to
      s          k      +      2        =            (                        x                      k            +            1                          ⁢                                  ⁢                  x          •                ⁢                                  ⁢                  y                      k            +            1                              )        ⁢          +      •        ⁢                  [                              (                                          x                k                            ⁢                                                          ⁢                                                                                                        ⁢                  x                                                                                                          ⁢                  •                                            ⁢                                                          ⁢                              y                k                                      )                    ⁢                      +            •                    ⁢                      s            k                          ]            .      Taking
            a      k        =                  x        k            ⁢                                                        ⁢          x                                                          ⁢          •                    ⁢                          ⁢              y        k            ⁢                          ⁢      and                          a                  k          +          1                    =                        x                      k            +            1                          ⁢                                  ⁢                  x          •                ⁢                                  ⁢                  y                      k            +            1                                ,                  s                  k          +          2                    =                        a                                    k              +              1                        ⁢                                                                ⁢                              +                                                                      •            ⁢                                                                ⁢                  (                                    a              k                        ⁢                                                  ⁢                          +              •                        ⁢                                                  ⁢                          s              k                                )                    is obtained. One also has
            s              k        +        2              =                  (                              s            k                    ⁢                      +            •                    ⁢                      a            k                          )            ⁢                          ⁢              +        °            ⁢                          ⁢              a                  k          +          1                      ,          ⁢            since      ⁢                          ⁢      operation        ⁢                  ⁢          +      °      is commutative.
The two operators MACk and MACk+1 can thus be replaced with a circuit 1 shown in FIG. 2C, receiving as an input three operands, ak, ak+1, and sk. ak corresponds to the saturating multiplication of operands xk and yk, ak+1 corresponds to the saturating multiplication of operators xk+1 and yk+1, and sk corresponds to the result of the preceding circuit. Circuit 1 provides a result sk+2 equal
      (                  s        k            ⁢                          ⁢              +        °            ⁢                          ⁢              a        k              )    ⁢          ⁢      +    °    ⁢          ⁢            a              k        +        1              .  The operations providing operands ak and ak+1 are executed outside of circuit 1.
A problem of known circuits of this type is that they perform complex processing steps and require significant hardware elements.
Thus, in prior art, one way of calculating sum
      s          k      +      2        =            (                        s          k                ⁢                                  ⁢                  +          °                ⁢                                  ⁢                  a          k                    )        ⁢                  ⁢          +      °        ⁢                  ⁢          a              k        +        1            is the following. The usual non-saturating sum of sk and ak is first calculated. Then, it is checked whether a saturation has occurred by means of an overflow circuit. If an upward overflow has occurred, the result of sum sk+ak is replaced with the maximum fractional number and if a downward overflow has occurred, the result of the sum is replaced with the minimum fractional number. Then, the normal addition of the obtained result with ak+1 is performed. Again, it is checked whether the result of the addition exceeds the limiting values allowed by the fractional representation and, if necessary, the necessary replacements are performed. In addition to the above-mentioned disadvantages, the calculation steps are long and require evaluating twice the upward and downward overflow of the result of an operation.